//
// Description: 5927. 反转偶数长度组的节点
// Created by Loading on 2021/11/14.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

// 反转部分链表，从 head 开始，到 end 的前一个节点结束
ListNode *reverseList(ListNode *head, ListNode *end) {
    ListNode *res = end;
    ListNode *curr = head;
    while (curr != end) {
        ListNode *ne = curr->next;
        curr->next = res;
        res = curr;
        curr = ne;
    }

    return res;
}

ListNode* reverseEvenLengthGroups(ListNode* head) {
    vector<vector<ListNode *>> v;
    ListNode *tmp = head;
    int index = 1;
    // 分组
    while (tmp) {
        vector<ListNode *> vec;
        for (int i = 0; i < index; ++i) {
            if (tmp) {
                vec.emplace_back(tmp);
            } else {
                break;
            }
            tmp = tmp->next;
        }
        ++index;
        v.emplace_back(vec);
    }

    for (int i = 0; i < v.size(); ++i) {
        if (v[i].size() % 2 == 0) {
            // 偶数长度组，反转
            if (i == v.size() - 1 && v[i - 1].size() % 2 == 0) {
                // 若最后两个组都需要反转，倒数第二组的储存的第一个节点为与最后一组的衔接点
                v[i - 1][0]->next = reverseList(v[i][0], v[i].back()->next);
            } else {
                // 上一个组没有反转，上一个组的储存的最后一个节点为下一个组的衔接点
                v[i - 1].back()->next = reverseList(v[i][0], v[i].back()->next);
            }
        }
    }

    return head;
}

int main() {
    auto head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    auto res = reverseEvenLengthGroups(head);
    while (res) {
        cout << res->val << " ";
        res = res->next;
    }
    cout << endl;

    return 0;
}